package Ep06_BinaryTree._0105;

import Ep06_BinaryTree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/5/31 13:53
 * 说明：lc 0105
 * 题目：
 *      给定两个整数数组preorder 和 inorder，其中preorder 是二叉树的先序遍历， inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 * 示例：
 *      输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 *      输出: [3,9,20,null,null,15,7]
 */

public class Mine {
    Map<Integer, Integer> map;      // 存储inorder中各个元素的index
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        // 全部遵循左闭右开
        return findNode(inorder, 0, inorder.length, preorder, 0, preorder.length);
    }

    private TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] preorder, int preBegin, int preEnd) {
        if (inBegin >= inEnd || preBegin >= preEnd) {
            return null;
        }
        int rootIndex = map.get(preorder[preBegin]);
        TreeNode root = new TreeNode(inorder[rootIndex]);
        int lenOfLeft = rootIndex - inBegin;

        // 递归
        root.left = findNode(inorder, inBegin, rootIndex, preorder, preBegin + 1, preBegin + 1 + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd, preorder, preBegin + lenOfLeft + 1, preEnd);
        return root;
    }
}
